import random
import heapq
import time
import numpy as np

# Chaque arête est dirigée et pèse des minutes
dict_reseau = {
    "Gare":      {"Centre": 5, "Musée": 6, "Université": 9},
    "Centre":    {"Musée": 2, "Hôpital": 4, "Rivière": 7},
    "Musée":     {"Théâtre": 3, "Centre": 3},
    "Université":{"Stade": 3, "Hôpital": 4},
    "Stade":     {"Parc": 5},
    "Hôpital":   {"Aéroport": 8, "Parc": 6},
    "Parc":      {"Rivière": 3},
    "Rivière":   {"Aéroport": 7, "Théâtre": 4},
    "Théâtre":   {"Centre": 4},
    "Aéroport":  {}
}

depart = ""
arrivee = ""
H = []              # Tas
distances = {}      # Distances
cles = {}           # Clés des éléments contenus dans le tas
X = []              # Liste pour stocker les vertex traités par l'algorithme